/**
 * @Question.Title: 除法求值
 * @Question.No: 399
 * @Author: DQ
 * @Date: 2021-02-01 16:59:38
 * @Description: 
 */
//给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values
//[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 
//
// 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj =
// ? 的结果作为答案。 
//
// 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替
//代这个答案。 
//
// 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。 
//
// 
//
// 示例 1： 
//
// 
//输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"]
//,["b","a"],["a","e"],["a","a"],["x","x"]]
//输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
//解释：
//条件：a / b = 2.0, b / c = 3.0
//问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
//结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
// 
//
// 示例 2： 
//
// 
//输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], quer
//ies = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
//输出：[3.75000,0.40000,5.00000,0.20000]
// 
//
// 示例 3： 
//
// 
//输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a
//","c"],["x","y"]]
//输出：[0.50000,2.00000,-1.00000,-1.00000]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= equations.length <= 20 
// equations[i].length == 2 
// 1 <= Ai.length, Bi.length <= 5 
// values.length == equations.length 
// 0.0 < values[i] <= 20.0 
// 1 <= queries.length <= 20 
// queries[i].length == 2 
// 1 <= Cj.length, Dj.length <= 5 
// Ai, Bi, Cj, Dj 由小写英文字母与数字组成 
// 
// Related Topics 并查集 图 
// 👍 458 👎 0

package unionfind.leetcode.editor.cn;

import com.dq.utils.CreateArray;

import java.util.*;

public class EvaluateDivision {
    public static void main(String[] args) {
        Solution solution = new EvaluateDivision().new Solution();
        String s1 = "[[\"a\",\"b\"],[\"e\",\"f\"],[\"b\",\"e\"]]";
        String s2 = "[[\"b\",\"a\"],[\"a\",\"f\"],[\"f\",\"f\"],[\"e\",\"e\"],[\"c\",\"c\"],[\"a\",\"c\"],[\"f\",\"e\"]]";
        List<List<String>> equations = create((String[][])CreateArray.genStrArray(s1.replace("\"","")));
        double[] values = new double[]{3.4,1.4,2.3};
        List<List<String>> queries = create((String[][])CreateArray.genStrArray(s2.replace("\"","")));
        double[] res = solution.calcEquation(equations,values,queries);
        System.out.println(Arrays.toString(res));
    }
    public static List<List<String>> create(String[][] s){
        List<List<String>> res = new ArrayList<>();
        for (String[] strings : s) {
            List<String> ll = new ArrayList<>();
            for (String string : strings) {
                ll.add(string);
            }
            res.add(ll);
        }
        return res;
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    Map<String, String> parent ;
    Map<String, Double> map;
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        parent = new HashMap<>();
        map = new HashMap<>();
        for(int i = 0; i < values.length; i++){

            List<String> temp = equations.get(i);
            union(temp.get(0),temp.get(1), values[i]);
        }

        return cal(queries,parent,map);
    }
    public double[] cal( List<List<String>> queries, Map<String, String> parent, Map<String, Double> map){
        double[] res = new double[queries.size()];
        for (int i = 0; i < res.length; i++) {

            List<String> query = queries.get(i);
            if(parent.get(query.get(0))!=null&&isConnect(query.get(0),query.get(1))){
                double one = getNum(query.get(0));
                double two = getNum(query.get(1));
                System.out.printf("(%s=%f, %s=%f)\n",query.get(0),one,query.get(1),two);
                res[i] = one/two;
            }else{
                res[i] = -1.0;
            }
        }
        return res;
    }
    public boolean isConnect(String x, String y){
        return getRoot(x).equals(getRoot(y));
    }
    public String getRoot(String x){
        if(parent.get(x) == null){
            return x;
        }
        //父节点和自己不一样
        while(!parent.get(x).equals(x)){
            String grandPa = parent.get(parent.get(x));
            map.put(x,map.get(x)*map.get(parent.get(x)));
            parent.put(x, grandPa);
            x = parent.get(x);
        }
        return x;
    }
    public double getNum(String x){
        if(x.equals("a")){
            System.out.println("a");
        }
        double n = 1.0;
        while(!parent.get(x).equals(x)){
            n *= map.get(x);
            x = parent.get(x);
        }
        return n;
    }

    public void union(String x, String y,  double value){

        String x_root = getRoot(x);
        String y_root = getRoot(y);
        if(x_root.equals(y_root)) return;
        // y <--- x
        parent.put(x_root, y_root);
        // x / y = val, x = val * y

        if (y.equals(y_root)) {
            parent.put(y_root,y_root);
            map.put(y_root,1.0);
        }

        map.put(x_root, getNum(x)*value/getNum(y));

    }

}
//leetcode submit region end(Prohibit modification and deletion)

}